//
//  572_另一棵树的子树.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/11.
/**
 https://leetcode.cn/problems/subtree-of-another-tree/description/
 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 */
// 遍历树，生成一个字符串 
import UIKit

class TreToStr: NSObject {
    func QA() {
        
    }
    func isSubtree(_ root: TreeNode<Int>?, _ subRoot: TreeNode<Int>?) -> Bool {
        let str1 = treeToStr(root)
        let str2 = treeToStr(subRoot)
        return str1.contains(str2)
    }
    
    func treeToStr(_ node: TreeNode<Int>?) -> String {
        guard let node = node else {
            return "#!"
        }
        let left = treeToStr(node.left)
        let right = treeToStr(node.right)
        return left + right + "\(node.val)!"
    }
}
